package com.shiguiwu.springmybatis.algorithm.sort;

/**
 * @description: 堆排序
 * 将待排序序列构造成一个大顶堆
 * 构造完后的整个序列的最大值就是堆顶的根节点
 * 将其与末尾元素进行交换，此时末尾就为最大值
 * 然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了
 * 可以看到在构建大顶堆的过程中，元素的个数逐渐减少，最后就得到一个有序序列了
 * 大顶堆和小顶堆的代码本质区别的公式 ：这边案例写的是大顶堆(升序)
 * 大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
 * 小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

 * @author: stone
 * @date: Created by 2021/11/2 15:55
 * @version: 1.0.0
 * @pakeage: com.shiguiwu.springmybatis.algorithm.sort
 */
public class HeapSort extends AbstractSort implements Sort {

    public static void main(String[] args) {
        int[] array = {3, 4, 2, 9, 8, 1};
        for (int i = array.length / 2 - 1; i >= 0; i--) {
            adjustHeap(array, i, array.length);
        }
    }

    public HeapSort(int[] array) {
        super(array);
    }

    @Override
    public void sort() {

    }

    /**
     * 将一个数组（二叉树），调整成一个大顶堆
     * @param array 数组
     * @param index 表非叶子节点在数组中的索引
     * @param length    表对多少个元素进行调整（length会逐渐减少，因为被调整好的增加了）
     */
    public static void adjustHeap(int[] array, int index, int length) {
        //先取出当前元素
        int temp = array[index];

        //开始调整。。。
        // 故：k = 2*i+1; 表示 k 是 i节点的左子节点
        for (int k = 2 * index + 1; k < length; k = 2 * k + 1) {//k=2*k+1 ,k 左子节点的左子节点
            // 说明左子节点的值，小于右子节点的值
            if (k + 1 < length && array[k] < array[k + 1]) {
                //正因为右子节点比较大，所以就换成是它来和当前节点比较
                k++;
            }

            //若子节点大于父节点的值
            if (array[k] > temp) {
                //把较大的值赋值给当前节点
                array[index] = array[k];
                //指向 k,继续比较(移动)
                index = k;
            }
            else {
                break;
            }

        }
    }
}
